#include<vector>
#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;

class Solution {
public:
	vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
		unordered_map<string, int> index;
		for (int i = 0; i < list1.size(); i++) {
			index[list1[i]] = i;
		}

		vector<string> ret;
		int indexSum = INT_MAX;
		for (int i = 0; i < list2.size(); i++) {
			if (index.count(list2[i]) > 0) {
				int j = index[list2[i]];
				if (i + j < indexSum) {
					ret.clear();
					ret.push_back(list2[i]);
					indexSum = i + j;
				}
				else if (i + j == indexSum) {
					ret.push_back(list2[i]);
				}
			}
		}
		return ret;
	}

	vector<string> findRestaurant2(vector<string>& list1, vector<string>& list2) {
		unordered_map<string, int> map;
		for (int i = 0; i < list1.size(); i++) {
			map[list1[i]] = INT_MAX;
		}
		for(int i=0;i<list2.size();i++){
			if (map.count(list2[i])) {
				int index = find(list1.begin(), list1.end(), list2[i]) - list1.begin();
				map[list2[i]] = i + index;
			}
		}
		int min = list1.size()+list2.size();
		vector<string> result;
		for (auto it = map.begin(); it != map.end(); it++) {
			if (it->second < min) {
				vector<string>().swap(result);
				result.push_back(it->first);
				min = it->second;
			}
			else if (it->second == min) {
				result.push_back(it->first);
			}
		}
		return result;
	}
};

void main() {
	vector<string> a1 = { "Shogun", "Tapioca Express", "Burger King", "KFC" }, a2 = { "KFC", "Burger King", "Tapioca Express", "Shogun" };
	vector<string> list1 = { "Shogun", "Tapioca Express", "Burger King", "KFC" }, list2 = { "Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun" };
	Solution s;
	s.findRestaurant2(a1, a2);
}